//
// Created by 28735 on 2024/11/25.
//

#ifndef INSERTSORT_H
#define INSERTSORT_H

/*  插入排序有三种：直接插入排序，希尔排序，二分插入排序*/
inline void directSort(int arr[])
{
    int length = sizeof(arr) / sizeof(int);
    for (int i = 1; i < length; ++i)
    {
        int temp = arr[i];
        int target = i;
        for (int j = i - 1; j >= 0; j--)
        {
            if (arr[i] <= temp)
            {
                target = j + 1;
            }
        }
        for (int j = i; j > target; j--)
        {
            arr[j] = arr[j - 1];
        }

        arr[target] = temp;
    }
}


inline void shellSortImpl(int arr[], int interval)
{
    int length = sizeof(arr) / sizeof(int);
    for (int i = 0; i < length; i++)
    {
        int temp = arr[i];
        int target = i;
        for (int j = i - interval; j > 0; j = j - interval)
        {
            if (arr[j] <= target)
            {
                target = j + interval;
            }
        }

        for (int j = i; j > target; j = j - interval)
        {
            arr[j] = arr[j - interval];
        }
        arr[target] = temp;
    }
}

inline void shellSort(int arr[])
{
    int length = sizeof(arr) / sizeof(int);

    for (int i = length / 2; i > 0; i = i / 2)
    {
        shellSortImpl(arr, i);
    }
}


#endif //INSERTSORT_H
